/*
题目: 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

    每一对相邻的单词只差一个字母。
     对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
    sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。
如果不存在这样的转换序列，返回 0 。
https://leetcode.cn/problems/word-ladder/
 */
public class LadderLength {
    Set<String> dict = new HashSet<> ();

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 双向广搜
        for (String s : wordList)   dict.add(s);
        if (beginWord.equals(endWord) || !dict.contains(endWord))  return 0;


        Queue<String> frontQue = new LinkedList<> ();
        Queue<String> backQue = new LinkedList<> ();
        Map<String, Integer> frontMap = new HashMap<> ();
        Map<String, Integer> backMap = new HashMap<> ();

        frontQue.offer(beginWord);
        frontMap.put(beginWord, 0);
        backQue.offer(endWord);
        backMap.put(endWord, 0);

        while (!frontQue.isEmpty() && !backQue.isEmpty()) {
            int ret = -1;
            if (frontQue.size() <= backQue.size()) {
                ret = update(frontQue, frontMap, backMap);
            } else {
                ret = update(backQue, backMap, frontMap);
            }

            // 求的是 转换序列 , 所以长度要 + 1
            if (ret != -1)  return ret + 1;
        }

        return 0;
    }

    private int update(Queue<String> queue, Map<String, Integer> map, Map<String, Integer> another) {
        int size = queue.size();
        while (size -- > 0) {
            String cur = queue.poll();
            char[] cs = cur.toCharArray();
            int steps = map.get(cur);

            // 对每一个字母进行 26 中替换, 如果某个单词在字典中, 那就入队
            for (int i = 0; i < cs.length; i ++) {
                char t = cs[i];

                for (char ch = 'a'; ch <= 'z'; ch ++) {
                    if (ch == t)    continue ;

                    cs[i] = ch;
                    String str = new String(cs);
                    // 如果字典里不在, 或者已经搜索过了
                    if (!dict.contains(str) || map.containsKey(str))    continue ;

                    // 第一次有交集
                    if (another.containsKey(str)) {
                        return steps + 1 + another.get(str);
                    } else {
                        map.put(str, steps + 1);
                        queue.offer(str);
                    }
                }

                cs[i] = t;
            }
        }
        return -1;
    }
}
